Nació como Paul Schneider y en algún momento adoptó una versión latinizada de su apellido (que en alemán significa "sastre"). En su ciudad natal estudió en la escuela primaria de San Lorenz, donde uno de sus maestros fue Leonhard Lechner. Luego, como explica en el prefacio de su "Neue Teutsche Liedlein", se fue a Italia para estudiar con algunos de los famosos compositores de la época. Probablemente se quedó por algún tiempo en Roma, en los círculos frecuentados por Palestrina y sus alumnos; un compositor que probablemente llegó a conocer bien fue Ruggiero Giovannelli, sobre cuyo motete "Jubilate Deo omnis terra" escribió una misa parodia. Hacia 1594 a más tardar, se convirtió en organista de la Hofkapelle del archiduque Maximiliano II de Austria, y ocupó este cargo hasta su muerte.

El archiduque vivió en Mergentheim, Franconia, hasta 1602 y posteriormente en Innsbruck, y por lo tanto Sartorius debe haber vivido principalmente en estos dos lugares. En 1599 envió una de sus misas de ocho partes al duque Maximiliano I de Baviera en Munich y más o menos al mismo tiempo envió  sus ocho "Magnificat" de seis partes y algunos motetes al arzobispo Wolf Dietrich von Raitenau en Salzburgo. Es impensable que su hogar permanente fuera Nuremberg, como Eitner supone; Eitner y algunas autoridades posteriores también lo identificaron erróneamente con el pastor Paul Nuremberg Sartorius (1561 a 1623); tampoco está relacionado con el editor de música de Nuremberg Johann Friedrich Sartorius.

Para un compositor alemán de la generación de Hassler, Sartorius estaba, como compositor de obras vocales sacras, muy puesto al día en su conocimiento de la música italiana. Fue menos influenciado por Lassus o Hassler que lo que fue por Palestrina. Esto es particularmente evidente en los ocho “Magnificat de seis partes”, en los que hizo uso no sólo de temas propios, sino incluso aquí y allá de pasajes enteros tomados de los "Magnificat" de Palestrina. Puso música sólo a los versos pares, comenzando por 'Et exultavit', y creó la impresión de un verdadero doble coro de ocho partes mediante el uso de grupos contrastantes de cuatro voces del coro completo. Sus canciones alemanas son casi en su totalidad en dos tiempos y utilizan principalmente ritmos de pavana y allemande, con texturas principalmente imitativas y mucha escritura secuencial. En forma y contenido están a medio camino entre el arte sofisticado de la canzoneta y la canción de danza sencilla.